package leetcode.DFS_BFS;

/**
 * @author mazouri
 * @create 2021-09-22 19:52
 */
public class _79_exist {
    char[][] board;
    char[] words;
    boolean[][] visited;
    int[] dX = {0, 1, 0, -1};
    int[] dY = {1, 0, -1, 0};
    boolean flag;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.words = word.toCharArray();
        this.visited = new boolean[board.length][board[0].length];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (words[0] == board[i][j]) {
                    dfs(i, j, 0);
                    if (flag) return true;
                }
            }
        }
        return flag;
    }

    private void dfs(int x, int y, int index) {
        if (index == words.length - 1) {
            flag = true;
            return;
        }

        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dX[i];
            int nextY = y + dY[i];
            if (isValid(nextX, nextY, index + 1)) {
                dfs(nextX, nextY, index + 1);
            }
        }
        visited[x][y] = false;
    }

    private boolean isValid(int x, int y, int index) {
        if (x >= board.length || x < 0 || y >= board[0].length || y < 0) return false;
        if (visited[x][y]) return false;
        return words[index] == board[x][y];
    }

    public static void main(String[] args) {
        char[][] b = {
                {'a', 'a'},
        };
        System.out.println(new _79_exist().exist(b, "aaa"));
    }
}
